/*
 * Copyright (c) 2022 Hong Jiahua
 * https://gitee.com/arrco/jh_dynamic_deque
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
/**
  * @file        jh_dynamic_deque.c
  * @brief       动态双端队列
  * @details     动态双端队列
  * @author      Hong Jiahua
  * @version     1.0.0
  * @date        2022-08-06
  * @copyright   2022 Hong Jiahua MIT License
  */
#include "jh_dynamic_deque.h"

/************************************************************************/
/*                                                                      */
/************************************************************************/
#define JH_DYNAMIC_DEQUE_DISABLE_ROUNDUP_POW_OF_TWO    0

#if JH_DYNAMIC_DEQUE_DISABLE_ROUNDUP_POW_OF_TWO
#   define jh_dynamic_deque_roundup_pow_of_two(_val)   (_val)
#else
#   if (__WORDSIZE == 64)
#       define jh_dynamic_deque_roundup_pow_of_two(_val) (--(_val), (_val)|=(_val)>>1, (_val)|=(_val)>>2, (_val)|=(_val)>>4, (_val)|=(_val)>>8, (_val)|=(_val)>>16, (_val)|=(_val)>>32, ++(_val), (_val))
#   else
#       define jh_dynamic_deque_roundup_pow_of_two(_val) (--(_val), (_val)|=(_val)>>1, (_val)|=(_val)>>2, (_val)|=(_val)>>4, (_val)|=(_val)>>8, (_val)|=(_val)>>16, ++(_val), (_val))
#   endif
#endif
/************************************************************************/
/*                                                                      */
/************************************************************************/
/**
  * @brief      判断动态双端队列是否为空
  * @param[in]  deque   动态双端队列
  *
  * @return     errcode
  * @retval      1      动态双端队列为空
  * @retval      0      动态双端队列不为空
  * @retval     -1      失败
  */
int jh_dynamic_deque_is_empty(jh_dynamic_deque_t* deque) {
    if(deque == NULL)
        return -1;
    
    return deque->head == deque->tail;
}

/**
  * @brief      判断动态双端队列是否已满
  * @param[in]  deque   动态双端队列
  *
  * @return     errcode
  * @retval      1      动态双端队列已满
  * @retval      0      动态双端队列未满
  * @retval     -1      失败
  */
int jh_dynamic_deque_is_full(jh_dynamic_deque_t* deque) {
    if(deque == NULL)
        return -1;
    
    return (deque->tail + 1) % deque->num == deque->head;
}

/**
  * @brief      获取动态双端队列的数据数量
  * @param[in]  deque   动态双端队列
  *
  * @return     errcode
  * @retval     >=0     动态双端队列的数据数量
  */
size_t jh_dynamic_deque_count(jh_dynamic_deque_t* deque) {
    if(deque == NULL)
        return 0;
    
    return (deque->tail + deque->num - deque->head) % deque->num;
}

/**
  * @brief      获取动态双端队列的大小
  * @param[in]  deque   动态双端队列
  *
  * @return     errcode
  * @retval     >=0     动态双端队列的数据大小
  */
size_t jh_dynamic_deque_size(jh_dynamic_deque_t* deque) {
    if(deque == NULL)
        return 0;
    
    return deque->num - 1;
}

/**
  * @brief      获取动态双端队列的容量
  * @param[in]  deque   动态双端队列
  *
  * @return     errcode
  * @retval     >=0     动态双端队列的数据容量
  */
size_t jh_dynamic_deque_capacity(jh_dynamic_deque_t* deque) {
    if(deque == NULL)
        return 0;
    
    return deque->capacity;
}

/**
  * @brief      数据添加到队首
  * @param[in]  deque   动态双端队列
  * @param[in]  item    要入队的数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_dynamic_deque_push_head(jh_dynamic_deque_t* deque, void* item) {
    if(deque == NULL || item == NULL || ((deque->tail + 1) % deque->num == deque->head))
        return -1;
    
    deque->head = deque->head ? deque->head - 1 : deque->num - 1;
    memcpy(deque->base + deque->head * deque->size, item, deque->size);
    
    return 0;
}

/**
  * @brief      数据添加到队尾
  * @param[in]  deque   动态双端队列
  * @param[in]  item    要入队的数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_dynamic_deque_push_tail(jh_dynamic_deque_t* deque, void* item) {
    if(deque == NULL || item == NULL || ((deque->tail + 1) % deque->num == deque->head))
        return -1;
    
    memcpy(deque->base + deque->tail * deque->size, item, deque->size);
    deque->tail = (deque->tail + 1) % deque->num;
    
    return 0;
}

/**
  * @brief      强制数据添加到队首
  * @param[in]  deque   动态双端队列
  * @param[in]  item    要入队的数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_dynamic_deque_force_push_head(jh_dynamic_deque_t* deque, void* item) {
    if(deque == NULL || item == NULL)
        return -1;
    
    if((deque->tail + 1) % deque->num == deque->head) {
        if (deque->num == deque->capacity) {
            deque->capacity = deque->capacity ? (deque->capacity << 1) : JH_DYNAMIC_DEQUE_INIT_CAPACITY;
            deque->base = jh_dynamic_deque_realloc(deque->base, deque->size * deque->capacity);
        }
        
        if(deque->num > 1) {
            memmove(deque->base + (deque->head + 1) * deque->size, deque->base + deque->head * deque->size, (deque->num - deque->head) * deque->size);
            memcpy(deque->base + deque->head * deque->size, item, deque->size);
            
            if(deque->tail > deque->head)
                deque->tail++;
        } else {
            memcpy(deque->base + deque->head * deque->size, item, deque->size);
            deque->tail++;
        }
        deque->num++;
    } else {
        deque->head = deque->head ? deque->head - 1 : deque->num - 1;
        memcpy(deque->base + deque->head * deque->size, item, deque->size);
    }
    
    return 0;
}

/**
  * @brief      强制数据添加到队尾
  * @param[in]  deque   动态双端队列
  * @param[in]  item    要入队的数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_dynamic_deque_force_push_tail(jh_dynamic_deque_t* deque, void* item) {
    if(deque == NULL || item == NULL)
        return -1;
    
    if((deque->tail + 1) % deque->num == deque->head) {
        if (deque->num == deque->capacity) {
            deque->capacity = deque->capacity ? (deque->capacity << 1) : JH_DYNAMIC_DEQUE_INIT_CAPACITY;
            deque->base = jh_dynamic_deque_realloc(deque->base, deque->size * deque->capacity);
        }
        
        if(deque->num > 1) {
            memmove(deque->base + (deque->head + 1) * deque->size, deque->base + deque->head * deque->size, (deque->num - deque->head) * deque->size);
            
            if(deque->tail > deque->head)
                deque->tail++;
            
            deque->head++;
        }
        deque->num++;
    }
    
    memcpy(deque->base + deque->tail * deque->size, item, deque->size);
    deque->tail = (deque->tail + 1) % deque->num;
    
    return 0;
}

/**
  * @brief      队首数据出队
  * @param[in]  deque   动态双端队列
  * @param[in]  item    要出队的数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_dynamic_deque_pop_head(jh_dynamic_deque_t* deque, void* item) {
    if(deque == NULL || item == NULL || deque->head == deque->tail)
        return -1;
    
    memcpy(item, deque->base + deque->head * deque->size, deque->size);
    deque->head = (deque->head + 1) % deque->num;
    
    return 0;
}

/**
  * @brief      队尾数据出队
  * @param[in]  deque   动态双端队列
  * @param[in]  item    要出队的数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_dynamic_deque_pop_tail(jh_dynamic_deque_t* deque, void* item) {
    if(deque == NULL || item == NULL || deque->head == deque->tail)
        return -1;
    
    deque->tail = deque->tail ? deque->tail - 1 : deque->num - 1;
    memcpy(item, deque->base + deque->tail * deque->size, deque->size);
    
    return 0;
}

/**
  * @brief      查看队首的数据
  * @param[in]  deque   动态双端队列
  * @param[in]  item    队首的数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_dynamic_deque_peek_head(jh_dynamic_deque_t* deque, void* item) {
    if(deque == NULL || item == NULL || deque->head == deque->tail)
        return -1;
    
    memcpy(item, deque->base + deque->head * deque->size, deque->size);
    
    return 0;
}

/**
  * @brief      查看队尾的数据
  * @param[in]  deque   动态双端队列
  * @param[in]  item    队尾的数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_dynamic_deque_peek_tail(jh_dynamic_deque_t* deque, void* item) {
    if(deque == NULL || item == NULL || deque->head == deque->tail)
        return -1;
    
    memcpy(item, deque->base + (deque->tail ? (deque->tail - 1) : (deque->num - 1)) * deque->size, deque->size);
    
    return 0;
}

/**
  * @brief      调整动态双端队列大小
  * @param[in]  deque   双端队列
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_dynamic_deque_resize(jh_dynamic_deque_t* deque, size_t num) {
    if(deque == NULL)
        return -1;
    
    num += 1;
    if(num > deque->num) {
        if (num > deque->capacity) {
            deque->capacity = num;
            deque->capacity = jh_dynamic_deque_roundup_pow_of_two(deque->capacity);
            deque->base = jh_dynamic_deque_realloc(deque->base, deque->size * deque->capacity);
        }
        size_t add_len = num - deque->num;
        memmove(deque->base + (deque->head + add_len) * deque->size, deque->base + deque->head * deque->size, (deque->num - deque->head) * deque->size);
        
        if(deque->tail > deque->head)
            deque->tail += add_len;
        
        deque->head += add_len;
        deque->num = num;
    } else if(num < deque->num) {
        size_t count = (deque->tail + deque->num - deque->head) % deque->num;
        if(count > (num - 1)) {
            deque->head = (deque->head + count - num + 1) % deque->num;
        }
        
        if(deque->head > 0) {
            if(deque->tail >= deque->head) {
                memmove(deque->base, deque->base + deque->head * deque->size, (deque->tail - deque->head) * deque->size);
                deque->tail = deque->tail - deque->head;
                deque->head = 0;
            } else {
                size_t sub_len = deque->num - num;
                memmove(deque->base + (deque->head - sub_len) * deque->size, deque->base + deque->head * deque->size, (deque->num - deque->head) * deque->size);
                deque->head -= sub_len;
            }
        }
        deque->num = num;
    }
    
    return 0;
}

/**
  * @brief      压缩动态双端队列的容量到合适大小
  * @param[in]  deque   动态双端队列
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_dynamic_deque_shrink_to_fit(jh_dynamic_deque_t* deque) {
    if(deque == NULL)
        return -1;
    
    size_t target_capacity = deque->num;
    target_capacity = jh_dynamic_deque_roundup_pow_of_two(target_capacity);
    if(target_capacity < deque->capacity) {
        deque->capacity = target_capacity;
        deque->base = jh_dynamic_deque_realloc(deque->base, deque->size * deque->capacity);
    }
    
    return 0;
}

/**
  * @brief      清空动态双端队列
  * @param[in]  deque   动态双端队列
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_dynamic_deque_clear(jh_dynamic_deque_t* deque) {
    if(deque == NULL)
        return -1;
    
    return deque->head = deque->tail = 0;
}

/**
  * @brief      获取动态双端队列指定位置的指定数量数据
  * @param[in]  deque   动态双端队列
  * @param[in]  item    获取的数据项
  * @param[in]  start   指定的起始位置
  * @param[in]  num     指定的数量
  *
  * @return     errcode
  * @retval     >=0     成功获取的数据数量
  * @retval     -1      失败
  */
int jh_dynamic_deque_get_data(jh_dynamic_deque_t* deque, void* item, size_t start, size_t num) {
    if(deque == NULL || item == NULL)
        return -1;
    
    size_t count = (deque->tail + deque->num - deque->head) % deque->num;
    if(start >= count)
        return 0;
    
    size_t vaild_len = (count - start) < num ? (count - start) : num;
    size_t all_tail_len = deque->tail > deque->head ? deque->tail - deque->head : deque->num - deque->head;
    size_t tail_len = all_tail_len > start ? ((all_tail_len - start) < vaild_len ? all_tail_len - start : vaild_len) : 0;
    memcpy(item, deque->base + (all_tail_len > start ? deque->head + start : 0) * deque->size, tail_len * deque->size);
    memcpy(item + tail_len * deque->size, deque->base + (all_tail_len > start ? 0 : start - all_tail_len) * deque->size, (vaild_len - tail_len) * deque->size);
    
    return vaild_len;
}

/**
  * @brief      动态双端队列数据排序
  * @param[in]  deque   动态双端队列
  * @param[in]  compare 指向用于比较两个数据项的函数指针
  *
  * @return     errcode
  * @retval     0       成功
  * @retval     -1      失败
  */
int jh_dynamic_deque_sort(jh_dynamic_deque_t* deque, int (*compare)(const void*, const void*)) {
    if(deque == NULL || compare == NULL)
        return -1;
    
    if(deque->tail < deque->head) {
        memmove(deque->base + deque->tail * deque->size, deque->base + deque->head * deque->size, (deque->num - deque->head) * deque->size);
        deque->tail += (deque->num - deque->head);
        deque->head = 0;
    }
    
    jh_dynamic_deque_qsort(deque->base + deque->head * deque->size, deque->tail - deque->head, deque->size, compare);
    
    return 0;
}

/**
  * @brief      动态双端队列创建
  * @param[in]  num     数组中能存放的数据项数量
  * @param[in]  size    数组中每个数据项的大小
  *
  * @return     jh_dynamic_deque_t* 动态双端队列
  * @retval     非NULL  成功
  * @retval     NULL    失败
  */
jh_dynamic_deque_t* jh_dynamic_deque_create(size_t num, size_t size) {
    jh_dynamic_deque_t* deque = jh_dynamic_deque_malloc(sizeof(jh_dynamic_deque_t));
    if(deque == NULL)
        return NULL;
    
    deque->num      = num + 1;
    deque->capacity = deque->num;
    deque->capacity = deque->num > JH_DYNAMIC_DEQUE_INIT_CAPACITY ? jh_dynamic_deque_roundup_pow_of_two(deque->capacity) : JH_DYNAMIC_DEQUE_INIT_CAPACITY;
    deque->size     = size;
    deque->head     = 0;
    deque->tail     = 0;
    
    deque->base = jh_dynamic_deque_malloc(size * deque->capacity);
    if(deque->base == NULL) {
        jh_dynamic_deque_free(deque);
        return NULL;
    }
    return deque;
}

/**
  * @brief      动态双端队列销毁
  * @param[in]  deque   动态双端队列
  *
  * @return     无
  */
void jh_dynamic_deque_destroy(jh_dynamic_deque_t* deque) {
    if(deque == NULL)
        return;
    
    jh_dynamic_deque_free(deque->base);
    jh_dynamic_deque_free(deque);
}
